
public class Leetcode668 {
    public double knightProbability(int n, int k, int row, int column) {

        // 表示剩余k步,处于位置ij处在棋盘的概率,
        Double[][][] cache = new Double[k + 1][n][n];
        // 最后得到在row,col处于k步在棋盘的概率
        double live = dfs(row, column, k, n, cache);
        // 8个方向的k步有8^k种排列
        double total = Math.pow(8, k);

        return live / total;
    }

    public double dfs(int x, int y, int k, int n, Double[][][] cache) {
        // 越界,概率是0
        if (x < 0 || y < 0 || x > n - 1 || y > n - 1) {
            return 0;
        }
        // 对于马最后没有步数可以移动情况下,在棋盘的的概率是1
        if (k == 0) {
            return 1;
        }

        if (cache[k][x][y] != null) {
            return cache[k][x][y];
        }

        double onBoard = 0;
        onBoard += dfs(x - 1, y - 2, k - 1, n, cache);
        onBoard += dfs(x - 1, y + 2, k - 1, n, cache);
        onBoard += dfs(x + 1, y - 2, k - 1, n, cache);
        onBoard += dfs(x + 1, y + 2, k - 1, n, cache);
        onBoard += dfs(x + 2, y - 1, k - 1, n, cache);
        onBoard += dfs(x - 2, y - 1, k - 1, n, cache);
        onBoard += dfs(x + 2, y + 1, k - 1, n, cache);
        onBoard += dfs(x - 2, y + 1, k - 1, n, cache);
        cache[k][x][y] = onBoard;

        return onBoard;
    }
}

